package com.wfm.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速选择
 * 时间复杂度：O(N) 算法导论证明说快速选择期望为线性的选择算法
 * 空间复杂度：O(logn) 递归使用栈空间期望就是O(logn)
 *
 */
public class P剑指OfferII076数组中的第K大的数字{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 由于默认从小到大排序，因此找到第k大的，下标是nums.length-k
        return quickSelect(nums,0,nums.length-1,nums.length-k);
    }
    public int quickSelect(int[] a, int l, int r, int index) {
        int p = partition(a, l, r);
        // 快速选择，就是不把所有区间都排序，而是根据index判断在哪个区间，然后排序那个区间
        if (p == index) {
            return a[p];
        } else if(p < index){
            return quickSelect(a, p + 1, r, index);
        }else {
            return quickSelect(a, l, p - 1, index);
        }
    }
    //left right 属于闭区间[]
    // 开始中枢选了left，最后返回的是中枢在最终排序完后，应该在哪个index
    // 虽然他左边都比他小，右边都比他大，但是左右并不是有序的
    public int partition(int[] nums,int left,int right){
        int pivot = left;
        while (left!=right){
            while (left<right&&nums[left]<nums[pivot]){
                left++;
            }
            while (left<right&&nums[right]>=nums[pivot]){
                right--;
            }
            swap(nums,left,right);
        }
        return left;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

//    底下都是partition的优化，或者区间的开闭的不同写法而已
//    Random random = new Random();
//    public int randomPartition(int[] a, int l, int r) {
//        int i = random.nextInt(r - l + 1) + l;
//        swap(a, i, r);
//        return partition(a, l, r);
//    }
//
//    // begin end 属于左闭右开区间[)
//    int partition2(int[] arr, int begin, int end)
//    {
//        int pivot = arr[begin];
//        while(begin < end)
//        {
//            while(begin < end && arr[--end] >= pivot);
//            arr[begin] = arr[end];
//            while(begin < end && arr[++begin] <= pivot);
//            arr[end] = arr[begin];
//        }
//        arr[begin] = pivot;
//        return begin;
//    }
//
//    // begin end 属于闭区间[]
//    int partition3(int[] arr, int begin, int end)
//    {
//        int pivot = arr[begin];
//        while(begin < end)
//        {
//            while(begin < end && arr[end] >= pivot) end--;
//            arr[begin] = arr[end];
//            while(begin < end && arr[begin] <= pivot) begin++;
//            arr[end] = arr[begin];
//        }
//        arr[begin] = pivot;
//        return begin;
//    }


    // 方法二 ：堆排序
//    public int findKthLargest(int[] nums, int k) {
//        int heapSize = nums.length;
//        buildMaxHeap(nums, heapSize);
//        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
//            swap(nums, 0, i);
//            --heapSize;
//            maxHeapify(nums, 0, heapSize);
//        }
//        return nums[0];
//    }
//
//    public void buildMaxHeap(int[] a, int heapSize) {
//        for (int i = heapSize / 2; i >= 0; --i) {
//            maxHeapify(a, i, heapSize);
//        }
//    }
//
//    public void maxHeapify(int[] a, int i, int heapSize) {
//        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
//        if (l < heapSize && a[l] > a[largest]) {
//            largest = l;
//        }
//        if (r < heapSize && a[r] > a[largest]) {
//            largest = r;
//        }
//        if (largest != i) {
//            swap(a, i, largest);
//            maxHeapify(a, largest, heapSize);
//        }
//    }
//
//    public void swap(int[] a, int i, int j) {
//        int temp = a[i];
//        a[i] = a[j];
//        a[j] = temp;
//    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] a = new int[]{4,5,3,6,2};
        Solution solution = new P剑指OfferII076数组中的第K大的数字().new Solution();
        int partition = solution.partition(a, 0, a.length);
        System.out.println(Arrays.toString(a));
//        System.out.println(partition);
    }
}